package goleetcode

func maxScore(nums []int, x int) int64 {
	// let dp[i] be the answer to the subarray nums[0...i]
	n := len(nums)
	memo := make([][2]int, n)
	for i := range memo {
		memo[i] = [2]int{-1, -1} // -1 代表没有计算过
	}
	var dfs func(int, int) int 
	dfs = func(i, j int) (res int) {
		if i == n {
			return
		}
		p := &memo[i][j]
		if *p != -1 {
			return *p
		}
		defer func() {
			*p = res
		}()
		if nums[i] % 2 != j {
			return dfs(i+1, j)
		}
		return max(dfs(i + 1, j), dfs(i + 1, j ^ 1) - x) + nums[i]
	}
	return int64(dfs(0, nums[0] % 2))
}